/**
 * @desc 350. Intersection of Two Arrays II
 * 
 * Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
 * 
 * 思路：
 *      挨着挨着比较
 *      [1,2,2,2]
 *      [1,2,2]
 *      当在arr2中找到符合的第一个2时，即break 不再需要遍历数组之后的
 *      同时在数组中删除这个相等的数。
 *  
 * 思考进阶：
 *      1.如果数组是有序的？怎么提高算法
 *      2.num1.size < num2.size
 */


/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
/*
var intersect = function(nums1, nums2) {
    let result = [];
    for(let i = 0;i<nums1.length;i++){
        for(let j = 0;j<nums2.length;j++){
            if(nums2[j]===nums1[i]){
                result.push(nums1[i]);
                nums2.splice(j,1);
                break;
            }
        }
    }
    return result;
};

let nums2 = [1, 2,2,1], nums1 = [2];
intersect(nums1,nums2);
*/

// 思路2 
// 如果数组有序
// 合并数组

/*
var intersect = function(nums1, nums2) {
    nums1.sort((a,b)=>a-b);
    nums2.sort((a,b)=>a-b);
    let 
        result = [],
        index1 = 0,
        index2 = 0;
    while(index1<nums1.length&&index2<nums2.length){
        if(nums1[index1]===nums2[index2]){
            result.push(nums1[index1]);
            index1++;
            index2++;
        }else if(nums1[index1]>nums2[index2]){
            index2++;
        }else{
            index1++;
        }
    }
    return result;
};
*/



// 思路3
// 对数组arr1建立不重复的hash表
// 即可查相同元素 又可计数不多push


var intersect = function(nums1, nums2) {
   let hash = {};
   let result = [];
   for(let i = 0;i<nums1.length;i++){
    //    if(!hash[nums1[i]]){
    //         hash[nums1[i]] = 1;
    //    }else{
    //         hash[nums1[i]]++;
    //    }
        hash[nums1[i]] = (hash[nums1[i]]||0) + 1;
   }

   for(let i = 0;i<nums2.length;i++){
        if(hash[nums2[i]]>0){
            result.push(nums2[i]);
            hash[nums2[i]]--;
        }
   }
   return result;
}

let nums1 = [1,2,2,2,1], nums2 = [2,1,2];
intersect(nums1,nums2);